class Solution:
    def calcEquation(
        self, equations: List[List[str]], values: List[float], queries: List[List[str]]
    ) -> List[float]:
        # 生成存储变量所构成的图结构
        graph = {}
        for (s, e), v in zip(equations, values):
            if s not in graph:
                graph[s] = {}  # 存储邻节点的哈希表
            graph[s][e] = v  # 生成一条s指向e，权重为v的路径，表示 s / e = v
            if e not in graph:
                graph[e] = {}
            graph[e][s] = 1 / v  # 生成一条反向路径，权重为1 / v，表示 e / s = 1 /v
            graph[s][s] = 1.0
            graph[e][e] = 1.0

        queue = []  # 用于广度优先搜索的队列
        n = len(queries)
        ans = [-1.0] * n  # 答案列表，初始都为-1表示未定义

        # 对于每个query，寻找从起点qx到终点qy的最短路径，并计算权重积
        for i, (qx, qy) in enumerate(queries):
            if qx not in graph or qy not in graph:
                continue  # 未出现的变量，跳过处理
            queue = [[qx, 1.0]]  # 初始将起点节点入队
            visited = set(
                [qx]
            )  # 存储已处理的节点；将qx放入列表表示存储整个字符串，否则会将字符串看成一个序列存储每个字母
            while queue:
                node, mul = queue.pop(
                    0
                )  # 获取当前处理的节点node以及到该节点所得到的权重积mul
                for neighbor, weight in graph[node].items():
                    # 枚举该节点的所有邻节点
                    if neighbor == qy:
                        ans[i] = (
                            mul * weight
                        )  # 找到终点，更新权重积后存储到答案并退出查找
                        break
                    if neighbor not in visited:  # 找到一个未处理的邻节点加入队列
                        visited.add(neighbor)
                        queue.append(
                            [neighbor, mul * weight]
                        )  # 将未处理的邻节点及到达该节点时的权重积加入队列
        return ans